package com.test.daily.leetcode.y2022.m06.day0608.v01;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/8 上午 09:38
 * @version: 1.0
 */
public class Solution {

    public static int bag1(int[] weights, int[] values, int w) {
        if (weights == null || weights.length == 0 || values == null || values.length == 0) {
            return -1;
        }
        return process(weights, values, 0, w);
    }

    public static int process(int[] weights, int[] values, int index, int w) {

        if (index == weights.length) {
            return 0;
        }
        if (w < 0) {
            return -1;
        }

        int p1 = process(weights, values, index + 1, w);
        int p2 = -1;
        int next = process(weights, values, index + 1, w - weights[index]);
        if (next != -1) {
            p2 = next + values[index];
        }

        return Math.max(p1, p2);
    }

    public static int bag2(int[] weights, int[] values, int w) {
        int N = weights.length;
        int[][] dp = new int[N + 1][w + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= w; j++) {
                dp[i][j] = -1;
            }
        }

        return process2(weights, values, 0, w, dp);

    }

    public static int process2(int[] weights, int[] values, int index, int w, int[][] dp) {

        if (dp[index][w] != -1) {
            return dp[index][w];
        }
        int ans = -1;

        if (index == weights.length) {
            ans = 0;
        } else if (w < 0) {
            ans = -1;
        } else {
            int p1 = process2(weights, values, index + 1, w, dp);
            int p2 = -1;
            int next = process2(weights, values, index + 1, w - weights[index], dp);
            if (next != -1) {
                p2 = next + values[index];
            }
            ans = Math.max(p1, p2);
        }
        dp[index][w] = ans;

        return ans;
    }

    public static int bag3(int[] weights, int[] values, int w) {
        // 測試bag3的
        if (weights == null || weights.length == 0 || values == null || values.length == 0) {
            return -1;
        }
        int N = weights.length;
        int[][] dp = new int[N + 1][w + 1];
        for (int i = 0; i <= w; i++) {
            dp[N][i] = 0;
        }
        for (int index = N - 1; index >= 0; index--) {
            for (int weight = 0; weight <= w; weight++) {
                int p1 = dp[index + 1][weight];
                int p2 = -1;
                int next = -1;
                if (w - weights[index] > 0) {
                    next = dp[index + 1][w - weights[index]];
                }
                dp[index][weight] = Math.max(p1, p2+next);
            }
        }
        return dp[0][w];
    }

    public static int process3(int[] weights, int[] values, int index, int w) {

        if (index == weights.length) {
            return 0;
        }
        if (w < 0) {
            return -1;
        }

        int p1 = process(weights, values, index + 1, w);
        int p2 = -1;
        int next = process(weights, values, index + 1, w - weights[index]);
        if (next != -1) {
            p2 = next + values[index];
        }

        return Math.max(p1, p2);
    }

}
